S3 Group

The S3 group is the group of permutation on 3 elements. It has 6 elements. It is the group of all the automorphism on the set {1, 2, 3}.

Here is the full list of the elements of S3:

## e: ()
## a: (1,2)
## b: (1,3)
## c: (2,3)
## p: (1,2,3)
## p^2: (1,3,2)

Table of S3:

S3	e	p	p2	a	b	c
e	e	p	p2	a	b	c
p	p	p2	e	c	a	b
p2	p2	e	p	b	c	a
a	a	b	c	e	p	p2
b	b	c	a	p2	e	p
c	c	a	b	p	p2	e

Order of the elements:

S3	Order	Sign	Inversions
e	1	+	0
p	3	+	0
p2	3	+	0
a	2	-	1
b	2	-	1
c	2	-	1

Unique normal chain decomposition of S3:

\[ C(2) \lhd C(3) \lhd S_3\]

And this decomposition is unique, the factors cannot be swapped.

Cycle graph

grViz('
graph cycle {
 graph[layout = neato]
 node [shape = circle, style = filled, color = grey, label=""]

 e [color = red]; a; b; c; p; p2

  e -- a
  e -- b
  e -- c
  e -- p -- p2 -- e
}
')

Subgroups of S3

###

is a normal subgroup

The group = {e, p, p2} is normal in S3:

all(p^a == p2, p^b == p2, p^c == p2)

## [1] TRUE

The classes of in S3 are:

{e, p, p2}, {a, b, c}

The action of a on : (p p2)

More detailed action of the group on :

S3	{e, p, p2}	{a, b, c}
e	{e, p, p2}	{a, b, c}
a	{a, b, c}	{e, p, p2}
b	{b, c, a}	{p2, e, p}
c	{c, a, b}	{p, p2, e}
p	{p, p2, e}	{c, a, b}
p2	{p2, e, p}	{b, c, a}

is isomorphic to Z/3Z and it has no non-trivial subgroups.

If G is a subgroup of S3 containing then G* is a subgroup of S3/. S3/ is a group of order 2 so it is isomorphic to Z/2Z and it has no non trivial subgroup. The only subgroups containing p are {e} and S3.

If G is a sub-group not including . Then inter(G, ) is {e}. because inter(G, ) is a subgroup of and it cannot be because G does no include .

So G is included in {e, a, b, c}. G cannot contain more than 2 elements because any of products ab, bc, … will yield an element of . So G is either {e, a}, {e, b}, {e, c}.

Conclusion: Here is the full list of the subgroups of S3: {e}, {e, a}, {e, b}, {e, c}, {e, p, p2}, {e, a, b, c, p, p2}

Lattice of all the subgroups

## Warning in .Call("R_igraph_layout_fruchterman_reingold", graph, coords, :
## '.Random.seed' is not an integer vector but of type 'NULL', so ignored

Normal subgroups

Actions of the group

The natural action of S3 on {1, 2, 3}

This is a faithful action.

We can compute the orbits:

S3	Orbits
e	{1} {2} {3}
a	{1, 2} {3}
b	{1, 3} {2}
c	{1} {2, 3}
p	{1, 2, 3}
p2	{1, 2, 3}

We can also compute the stabilizers:

{1, 2, 3}	Stabilizer
1	<c>
2	<b>
3	<a>

Action on the ‘edges’

We consider the action of S3 on this set: {{1, 2}, {1, 3}, {2, 3}}

Action of

## [1] TRUE

Action of a:

all(
  a_f(c(1, 2)) == c(2, 1),
  a_f(c(1,3)) == c(2, 3),
  a_f(c(2, 3)) == c(1, 3))

## [1] TRUE

Since a and p generate S3 we deduce that the action is faithfull.

Orbits

S3	Orbits
e	{1_2} {1_3} {2_3}
a	{1_2} {1_3, 2_3}
b	{1_2, 2_3} {1_3}
c	{1_2, 1_3} {2, 3}
p	{1_2, 2_3, 1_3}
p2	{1_2, 2_3, 1_3}

Stabilizers

Action on the elements of order 2

The elements of order 2 are: a, b, c

c(a^p == c, a^(p^2) == b)

## [1] TRUE TRUE

So the action is transitive. And |O(a)|.|Stab(a)| = 6 => 3.|Stab| = 6 So the stabilizer size is 2.

And:

S3	Stab
a	e, a
b	e, b
c	e, c

Action on the elements of order 3

The elements of order 3 are: p, p^2

c(p^a == p^2)

## [1] TRUE

So the action is transitive and: |O(p)|.|Stab(p)| = 6 so |Stab(p)| = 2

S3	Stab
p	e, p, p2
p2	e, p, p2

Beat actions

Let f be a recording, and g a permutation of the indices of the recording. fâ is the image of f by g if the index 2 of fâ is the index i of f such that g(i) = 2. So i=gâ1(2) i=gâ1(2) We define \(g \bullet f = f' = f \circ g\) Which means that \(f'(1) = f(g(1))\) Or more generally \(f'(i) = f(g(i))\) Letâs write a function that applies a permutation to a recording.

apprec <- function(gp) {
  function(...) {
    f <- c(...)
    f[as.word(gp) %>% unclass %>% c]
  }
}

Let’s check the relationship \(f'(1) = f(g(1))\) with \(g = (123456)\), and f = 100000. We should have \(f'(1) = f(g(1)) = f(2) = 0\) and \(f'(6) = f(g(6)) = f(1) = 1\)

g <- as.cycle(1:6)
all(
  apprec(g)(1, 0, 0, 0, 0, 0) == c(0, 0, 0, 0, 0, 1))

## [1] TRUE

Definition

S3 has an action on

Beat	1	2	3	4	5	6
p	3	1	2	6	4	5
a	1	2	3	4	6	5
p2	2	3	1	5	6	4
apa	3	1	2	5	6	4

This convention means that the action of p is given by 1->3, 2->1, 3->2… We can read the action directly from this table by interpreting in terms of indices: p(1) = 3 can be translated as: the value at index 1 is moved to index 3.

This is an action because: \[g \circ^{op} h \bullet f|_i = f_{gh(i)} = f_{h(g(i))} = g \bullet (h \bullet f)|_i\] This action can be written as a morphism \(M: S(1 \dots 6)^{op} \rightarrow S(Rec)\)

And we have the following property: \[ M(g \circ^{op} h)(f) = M(g \cdot h)(f) = M(g)(M(h)(f))\] So \(M(g \cdot h) = M(g) \circ M(h)\)

We can check this relationship with gp = (123)(456), ga = (14)(26)(35) and 100000 \(M((123)(456) \cdot (14)(26)(35))(100000) = M((16)(25)(34))(100000) = 000001\) \(M((123)(456) \cdot (14)(26)(35))(100000) = M((123)(456)) \circ M((14)(26)(35))(100000) = M((123)(456))(000100) = 000001\)

gp <- as.cycle(1:3) * as.cycle(4:6)
ga <- as.word(c(4, 6, 5, 1, 3, 2))
all(
  apprec(gp * ga)(1, 0, 0, 0, 0, 0) == apprec(gp)(apprec(ga)(1, 0, 0, 0, 0, 0)))

## [1] TRUE

The action of p circulates the 2 3-blocks. It has 2 orbits. The action of a on the first 3-block is the trivial one. On the second 3-block it switches 5 and 6.

In order to define the action we remember this following presentation of S3: \(<a^2, p^3, apa = p^2>\)

Check that the action on the first row is an action: \(\phi_1(a) = (1 4) (2 5) (3 6)\) \(\phi_1(p) = id\)

The images verify all the relations, so it is indeed an action.

Check that the action on the second row is an action: \(\phi_2(a) = (5 6)\) \(\phi_2(p) = (1 2 3) (4 5 6)\)

gp <- as.cycle(1:3) * as.cycle(4:6)
ga <- as.cycle(5:6)

So apparently this is not an action since gp^ga != gp^2

gp^ga == gp^2

## [1] FALSE

We can try this one:

Beat	1	2	3	4	5	6
a.2	4	5	6	1	3	2

We have for the second row:

ga <- as.word(c(4, 5, 6, 1, 3, 2))

This also doesn’t work since ga^2 is not identity.

What about this one?

Beat	1	2	3	4	5	6
p.2	2	3	1	5	6	4
a.2	4	6	5	1	3	2

ga <- as.word(c(4, 6, 5, 1, 3, 2))
cat('ga: ', as.character(as.cycle(ga)), '\r\n')

## ga:  (1,4)(2,6)(3,5)

cat('gp: ', as.character(as.cycle(gp)))

## gp:  (1,2,3)(4,5,6)

We have:

c(gp^3 == as.cycle(), 
  ga^2 == as.cycle(),
  gp^ga == gp^2)

## [1] TRUE TRUE TRUE

So it is an action of S3

Beat	1	2	3	4	5	6
e	1	2	3	4	5	6
a	4	6	5	1	3	2
p	2	3	1	5	6	4
p2	4	6	5	1	3	2
ap	5	4	6	2	1	3
ap2	6	5	4	3	2	1

Automorphism of the action

Let \(\eta:Rec \rightarrow Rec\) where Rec is the set of all recordings of this action. We let \(\eta(f)_i=1+f_i\) That is if \(f_i=1\) then \(\eta(f)_i=0\) and if \(f_i=0\) then \(\eta(f)i=1\)

We can easily show that Î· is injective, surjective and itâs inverse is itself.

Furthermore we can show that Î· is a group action morphism: \(\eta(g \bullet f)_i = 1 + (g \bullet f)_i = 1 + f_{g(i)}\) and \(g \bullet \eta(f)|_i = \eta(f)_{g(i)} = 1 + f_{g(i)}\)

In particular Î· is a bijection between beats.

Decomposition into orbits

Assuming each slot can be 0 or 1 there are 2^6 = 64 sounds.

Beats are orbits of recording under the previously defined action.

We can differentiate beats according to how many sounds they contain.

We can classify the beats by the number of records they contain which we call the beats size.

|O|.|Stab| = 6 So the size of the beats is either 1, 2, 3 or 6.

Classification of the beats of size 1

Let B be a bit of size 1 and f the only recording inside that beat. Then we have: \(p \bullet f = f \implies p \bullet f|_1 = f(1) \implies f_{p1} = f(1) \implies f_2 = f_1\)

Duplicating this with p2, a, ap, ap2 yields respectively f(3) = f(1), f(4) = f(1), f(5) = f(1), f(6) = f(1).

In the end we have shown that f is constant which means f = 0 or f = 1. Both solution works so we have shown that there are exactly 2 beats of size 1.

0 0 0 0 0 0 and
1 1 1 1 1 1

Classification of the beats of size 2

Let B be a bit of size 2. We can write B = {f, g}. We have Stab(f) = Stab(g) = {e, p, p2}.

\[p \bullet f = f \textrm{ and } p^2 \bullet f = f \implies \\ f(1) = f(2) = f(3) \textrm{ and } f(4) = f(5) = f(6)\]

So f is of the form (x,x,x,y,y,y). Furthermore we must have \(x \neq y\) because otherwise B would have size 1. So finally f is one of:

0 0 0 1 1 1
1 1 1 0 0 0

Both of those have size 2, and they belong to the same beat. So there is exactly 1 beat of size 2

Classification of the beats of size 3

Let B be a bit of size 3.

1. First we will show that we can find a record in B of the form (x, y, z, x, z, y) where x, y, z are not all equal

f a record in B. We have |Stab(f)| = 2 so Stab(f) = {e, a} or {e, ap} or {e, ap2}.

Let’s assume Stab(f) = {e, a}. Then \(a \bullet f = f\). If we have also p.f = f Then B has size 1 which is absurd. So we have \(p \bullet f \neq f\) and \(\phi(p)\) has order 3 which means B = {f, pf, p2.f}

a.f = f implies (f(4), f(6), f(5), f(1), f(3), f(2)) = (f(1), f(2), f(3), f(4), f(5), f(6))

So: f(4) = f(1), f(5) = f(3), f(6) = f(2)

Furthermore we canno’t have f(1) = f(2) = f(3) otherwise f would be constant and the beat would have size 1.

So the analysis says that f is of the form (x, y, z, x, z, y) where x, y, z are not all equal.

For example (1, 0, 0, 1, 0, 0) or (0, 1, 0, 0, 0, 0, 1) or (1, 1, 0, 1, 0, 1)

2. Here we will show that a function of the above form indeed spans a beat of size 3

Let’s assume that f is of this form. Then clearly \(p \bullet f \neq f\) and \(a \bullet f = f\) so Stab(f) = {e, a}. So the beat of f has size 3.

3. Here we will show that 2 different function of the above form cannot share the same beat

Let g be another function of this form (x, y, z, x, z, y) and suppose g is in O(f). Then g = pf or g = pf2. Let’s assume g = pf. Then g = (z, x, y, y, x, z)

So we can deduce z = y: f = (x, y, y, x, y, y) and g = (y, x, y, y, x, y) Furthermore we still have a.g = g so in particular g(5) = g(3) which means x = y. So in the end x = y = z which is absurd. So that means g is not in O(f).

4. Conclusion on beats of size 3

Total number of beats is the total number of triplets (x, y, z) minus the 2 constant triplets \(2*2*2 - 2 = 6\). So there are 6 beats of size 2. They are:

1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 0
0 1 1 0 1 1
1 0 1 1 1 0
1 1 0 1 0 1

Classification of the beats of size 6

Let n be the number of 6 beats. We have \(64=2+1*2+6*3+n*6\) so n = 7. We can see that the function \(card: f \mapsto \sum_{1 \leq i \leq 6}f(i)\) is a beat invariant.

\(\forall g \in S3, f \in \textrm{Rec}, card(g \bullet f) = card(f)\) So we can classify the beats of size 6 by their cardinal.

1. If a beat has cardinal 0 then it is constant So it cannot be of size 6

asda

2. If a beat has cardinal 1 

Let B be a beat of cardinal size 1, f be a recording in B.

There is a unique index i that gives the place of the unique 1 in f. We can find an element that acts on f that maps i to 1. For example if i = 4, a will do, if i = 5, ap will do… So we can assume f to be 1 0 0 0 0 0. We can check that the beat of f is of size 6. So there is only 1 beat of cardinal 1 of size 6.
1 0 0 0 0 0

3. If a beat has cardinal 2

Similar to the previous cardinal we can always find a beat representent which starts with a 1. That means that there are at most 5 beats:

1 1 0 0 0 0
1 0 1 0 0 0 = p . 1 1 0 0 0 0 1 0 0 1 0 0 Orbit has size 3 (a is in stabilizer)
1 0 0 0 1 0 Orbit has size 3 (ap is in stabilizer)
1 0 0 0 0 1 Orbit has size 3 (ap2 is in stabilizer)

all(apprec(gp)(1, 1, 0, 0, 0, 0) == c(1, 0, 1, 0, 0, 0))

## [1] TRUE

So there is only 1 possible beat of cardinal 2 and size 6. which is: 1 1 0 0 0 0, 0 1 1 0 0 0, 1 0 1 0 0 0, 0 0 0 1 0 1, 0 0 0 0 1 1, 0 0 0 1 1 0

4. If a beat has cardinal 3.

Let f be a recording. We can choose it such that it starts with a 1. So we have 10 possibilities

1 1 1 0 0 0 Orbit has size 2  
1 1 0 1 0 0  
1 1 0 0 1 0  
1 1 0 0 0 1  
1 0 1 1 0 0 = p2 . 1 1 0 0 1 0  
1 0 1 0 1 0 = p2 . 1 1 0 0 0 1  
1 0 1 0 0 1 = p2 . 1 1 0 1 0 0  
1 0 0 1 1 0 = ap . 1 1 0 0 1 0  
1 0 0 1 0 1 = a . 1 1 0 1 0 0  
1 0 0 0 1 1 = ap2 . 1 1 0 0 0 1

all(apprec(gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 1, 1, 0, 0),
    apprec(gp)(1, 1, 0, 0, 0, 1) == c(1, 0, 1, 0, 1, 0),
    apprec(gp)(1, 1, 0, 1, 0, 0) == c(1, 0, 1, 0, 0, 1),
    apprec(ga*gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 0, 1, 1, 0),
    apprec(ga)(1, 1, 0, 1, 0, 0) == c(1, 0, 0, 1, 0, 1),
    apprec(ga*gp^2)(1, 1, 0, 0, 0, 1) == c(1, 0, 0, 0, 1, 1))

## [1] TRUE

So we have at most 3 beats of cardinal 3 and size 6. We verify that each of those 3 recording span distinct beats and that they each have size 6

5. If a beat has cardinal 4

Let B be a beat of cardinal 4, we verify that \(\eta(B)\) is a beat of cardinal 2. Since \(\eta\) is a bijection preserving beats we know that it gives a correspondance between beats of cardinal 2 and beats of cardinal 4. So there is only one beat of cardinal 4. And it is given by:
0 0 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1
1 1 1 0 1 0 <- I like this one
1 1 1 1 0 0
1 1 1 0 0 1

6. Beat of cardinal 5

Let B be a beat of cardinal 4, we verify that $\eta(B)$ is a beat of cardinal 2. Since $\eta$ is a bijection preserving beats we know that it gives a correspondance between beats of cardinal 1 and beats of cardinal 5. So there are only one beat of cardinal 5. And it is given by: **1 1 1 1 1 0**

Conclusion

Beat size	Number
1	2
2	1
3	6
6	7

Beat representant	Beat size
1 1 1 1 1 1	1
0 0 0 0 0 0	1
1 1 1 0 0 0	2
1 0 0 1 0 0	3
0 1 0 0 0 1	3
0 0 1 0 1 0	3
0 1 1 0 1 1	3
1 0 1 1 1 0	3
1 1 0 1 0 1	3
1 0 0 0 0 0	6
1 1 0 0 0 0	6
1 1 0 1 0 0	6
1 1 0 0 1 0	6
1 1 0 0 0 1	6
1 1 1 0 1 0	6
1 1 1 1 1 0	6

Other actions

The action of S3 on S3/ is not faithfull. S3/ = {{e, p, p2}, {a, b, c}} Any element of is sent to the identity. Any other element is sent to ({e, p, p2} {a, b, c})
There is also an action of S3 on {a, b, c}.
And an action of S3 on

All the transitive, faithfull actions of S3

Let \(\phi\) be a transitive, faithfull set action \(S3 \rightarrow S(\mathcal{A})\). Where \(\mathcal{A}\) is any set. We note: \(g \bullet x = \phi(g)(x)\) for \(g \in S3, a \in \mathcal{A}\)

First we would like to show that \(\mathcal{A}\) has 6 elements.

Let \(a_0 \in \mathcal{A}\), we let \(f_{a_0}: S3 \rightarrow \mathcal{A}\) defined by \(f_{a_0}(g) = g \bullet a_0\)

Since the action is transitive \(f_{a_0}\) is surjective. Let’s \(g_1, g_2 \in \mathrm{S3}\). \[f_{a_0}(g_1) = f_{a_0}(g_2) \iff g_1 \bullet a_0 = g_2 \bullet a_0 \iff g_1 g_2^{-1} \bullet a_0 = a_0\]

How to see if 2 actions are isomorphic?

In all this file G is a finite group and S is a set.

An action is a group morphism \(\phi_1: G \rightarrow Aut(S)\) where S is some set. Let \(\phi_2: G \rightarrow Aut(S2)\) be another group action. 2 action are isomorphic iff there exist a set isomorphism \(f: S \rightarrow S2\) such that \[\forall g \in G, f(\phi_1(g)(x)) = \phi_2(g)(f(x))\]

The next property shows that if we have verified the property on f for \(g_1, g_2 \in G\), then the property holds for \(g_1g_2\). \[f(\phi_1(g_1g_2)(x)) = f(\phi_1(g_1)(\phi_1(g_2)(x))) = \phi_2(g_1)(f(\phi_1(g_2)x)) = \phi_2(g_1)(\phi_2(g_2)(fx)) = \phi_2(g_1g_2)(fx)\]

That means that we only need to verify the property on a set of generators for G.

Example

Let’s show that the action on {1, 2, 3} is isomorphic to the action on {{1, 2}, {1, 3}, {2, 3}} by taking f: 1 -> {2, 3} f: 2 -> {1, 3} f: 3 -> {1, 2}

f(p.1) = f(2) = {1, 3} p.f(1) = p.{2, 3} = {1, 3}

f(p.2) = f(3) = {1, 2} p.f(2) = p.{1, 3} = {1, 2}

f(a.1) = f(2) = {1, 3} a.f(1) = a.{2, 3} = {1, 3}

f(a.3) = f(3) = a.f(3) => f(3) = {1, 2}

f(b.2) = f(2) = b.f(2) => f(2) = {1, 3}

f(c.1) = f(1) = c.f(1) => f(1) = {2, 3}

So f is an isomorphism of actions.

Automorphism group of S3

Inner automorphisms

Conjugation by an element creates an automorphism. The conjugation by p has the following effect:

## a^p: (2,3)
## b^p: (1,2)
## c^p: (1,3)
## p^p: (1,2,3)
## p2^p: (1,3,2)

So conj(p) = (a c b)

Here is the conjugation by p2:

## a^p2: (1,3)
## b^p2: (2,3)
## c^p2: (1,2)
## p^p2: (1,2,3)
## p2^p2: (1,3,2)

So conj(p2) = (a b c)

Here is the conjugation by a:

## a^a: (1,2)
## b^a: (2,3)
## c^a: (1,3)
## p^a: (1,3,2)
## p2^a: (1,2,3)

So conj(a) = (b c) (p p2)

Here is the conjugation by b:

## a^b: (2,3)
## b^b: (1,3)
## c^b: (1,2)
## p^b: (1,3,2)
## p2^b: (1,2,3)

So conj(b) = (a c) (p p2)

Here is the conjugation by c:

## a^c: (1,3)
## b^c: (1,2)
## c^c: (2,3)
## p^c: (1,3,2)
## p2^c: (1,2,3)

So conj(c) = (a b)(p p2)

So together with the identity there are 6 inner automorphisms.

Structure of the automorphism group

We will show that Inner(S3) = S3 conj(a)^2 = e conj(p)^3 = e conj(p)^conj(a) = conj a-1 o conj p o conj a = conj a-1pa = conj p2 = conj(p)^2

Since the generators of Inner(S3) have the same relations as those of S3 we know the 2 groups are isomorphic.

Total group or isomorphism

We can show that there are no outer isomorphism. Indeed an automorphism maps elements to elements of the same order. There are thus 2 possibilities for mapping p and 3 possibilities for mapping a. Since a and p generate S3 this 2 images will define uniquely a mapping. There are at most 3*2 automorphisms and according to the previous paragraphs we already have 6 inner automorphisms. So all the automorphism are inner.

Matrix representation of an automorphism

Since an automorphism is uniquely defined by its image of the generators a and p we might be able to write them as a matrix. Indeed the reason we are able to write linear operators as matrix is because they are defined by their action on a basis which is a generator set of the whole vector space.

First lets try to write elements of S3 as vectors: we note a = (1, 0) and p = (0, 1) (0, x) * (1, m) = p^x * a * p^m = a * a p^x * a p^m = (1, 2*x+m)

(g1, n1) * (g2, n2) = g1n1g2n2 = g1g2inv(g2)n1g2n2 = g1g2n1^g2n2 = (g1g2, n1^g2*n2)

inv(g1) * (g2, n2) * g1 = inv(g1) * (g2*g1, n2^g1) = (g2^g1, n2^g1) conj(g1) = g1 e e g1